package testing;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Iterator;
import java.util.Random;

public class OnTheFlyGaussianElimination {
	public int k = 5;
	public int n = 20;
	public int[][] matrix = new int[k][n];
	public ArrayList<Integer> index = new ArrayList<Integer>();
	public int numOnes[] = null;
	int[] serverInserted = null;
	public int[][] transpose = new int[n][k];
	public int[][] G = new int[k][k];

	// int[][] transpose = {{0, 0, 1, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 1, 1, 1},
	// {0, 0, 1, 1, 0}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 1, 0, 0}};

	public int[] serverAvailability() {
		int[] servers = new int[n];
		Random random = new Random();
		for (int i = 0; i < n; i++) {
			if (random.nextDouble() < 0.8) {
				servers[i] = 1;
			} else {
				servers[i] = 0;
			}
			System.out.print(" " + servers[i]);
		}

		return servers;

	}

	public int[][] identity(int N) {
		int[][] I = new int[N][N];
		for (int i = 0; i < N; i++)
			I[i][i] = 1;
		return I;
	}

	public int[][] createGeneratorMatrix() {
		Random random = new Random();

		for (int outerIndex = 0; outerIndex < matrix.length; outerIndex++) {
			for (int innerIndex = 0; innerIndex < matrix[outerIndex].length; innerIndex++) {
				if (random.nextDouble() < 0.5) {
					matrix[outerIndex][innerIndex] = 1;
				} else {
					matrix[outerIndex][innerIndex] = 0;
				}
			}
		}
		return matrix;
	}

	public int[][] matrixTranspose(int[][] generator) {
		int[][] transpose;
		int rows = k;
		int cols = n;
		transpose = new int[cols][rows];

		for (int h = 0; h < rows; h++) {
			for (int i = 0; i < cols; i++) {
				transpose[i][h] = generator[h][i];
			}
		}

		return transpose;
	}

	/*
	 * b- equation for every encoded packet
	 */
	public ArrayList<Integer> decodeOnTheFly(int[][] b, int idx) {
		// ArrayList<Integer> sourceIndex= new ArrayList<Integer>();

		int emptyRows = k - 1;

		int[] eqn = new int[k];
		int eqOnes = 0;
		int leftMost = 0;
		int leftMostPos = 0;
		int i = -1;
		int firstExecution = 0;
		int indexForInsertion = 0;
		int position = 0;
		// for (int i = 0; i < 7; i++) {
		// numOnes.ensureCapacity(k);
		if (index.isEmpty()) {
			firstExecution = 1;
			emptyRows = k;
			numOnes = new int[k];
			/*
			 * array to keep track of which server index is finally actually
			 * inserted at which position within the G matrix
			 */
			serverInserted = new int[k];
			position = -1;
		} else {
			emptyRows = 1;
			indexForInsertion = idx;
			// i=index.get(k-1);
			Object max = Collections.max(index);
			i = (Integer) max;

			for (int z = 0; z < k; z++) {
				if (serverInserted[z] == idx) {
					serverInserted[z] = 0;
					for (int j = 0; j < k; j++) {
						G[z][j] = 0;
					}
					indexForInsertion = z;
					break;
				}
			}
			// TODO add code here to find the index of the server which needs o
			// be removed from serverInserted and set the corresponding entry to
			// 0 in G matrix
			i = -1;
			numOnes[indexForInsertion] = 0;
		}
		int swapped = 0;

		while (emptyRows > 0 && i <= n - 2) {
			int tempServer = 0;
			i++;
			swapped = 0;
			eqOnes = 0;
			leftMost = 0;
			leftMostPos = 0;
			/*
			 * eqn = extract one row from the generator matrix
			 */
			for (int j = 0; j < k; j++) {
				eqn[j] = b[i][j];
				if (eqn[j] == 1) {
					eqOnes++;
					if (leftMost == 0) {
						leftMost = 1;
						leftMostPos = j;
					}
				}
			}
			while (G[leftMostPos][leftMostPos] == 1 && eqOnes > 0) {
				if (eqOnes >= numOnes[leftMostPos]) {
					/*
					 * eqn'=xor G[s] and eqn
					 */
					for (int l = 0; l < k; l++) {
						eqn[l] = (eqn[l] + G[leftMostPos][l]) % 2;
					}
				} else {
					/*
					 * swap eqn and G[s]
					 */
					int temp;
					for (int l = 0; l < k; l++) {
						temp = eqn[l];
						eqn[l] = G[leftMostPos][l];
						G[leftMostPos][l] = temp;
					}
					tempServer = serverInserted[leftMostPos];
					serverInserted[leftMostPos] = i;
					numOnes[leftMostPos] = eqOnes;
					swapped = 1;
				}
				/*
				 * calculate left most 1 in eqn and degree of eqn'( numOfOnes)
				 */
				leftMost = 0;
				leftMostPos = 0;
				eqOnes = 0;
				int l = 0;
				while (l < k) {
					if (eqn[l] == 1) {
						if (leftMost == 0) {
							leftMostPos = l;
							leftMost++;
						}
						eqOnes++;
					}
					l++;
				}
			}
			if (eqOnes > 0) {
				if (firstExecution == 1) {
					/*
					 * add eqn to G[s], gDegree=numOfOnes, emptyRows=emptyRows-1
					 */
					for (int m = 0; m < k; m++) {
						G[leftMostPos][m] = eqn[m];
					}
					numOnes[leftMostPos] = eqOnes;
					// gDegree = numOfOnes;
					emptyRows = emptyRows - 1;
					System.out.print("\n" + i);
//					index.add(i);
					position++;
					if (swapped == 1) {
						serverInserted[position] = tempServer;
						swapped = 0;
					} else
						serverInserted[position] = i;
				} else {
					if (!index.contains(i)) {
						for (int m = 0; m < k; m++) {
							G[leftMostPos][m] = eqn[m];
						}
						index.remove(indexForInsertion);
						index.add(indexForInsertion, i);
						numOnes[k - 1] = eqOnes;
						emptyRows = emptyRows - 1;

						if (swapped == 1) {
							serverInserted[indexForInsertion] = tempServer;
							swapped = 0;
						} else {
							serverInserted[indexForInsertion] = i;
						}
					}
				}
			} else {
				/*
				 * discard eqn
				 */
			}

		}
		System.out.println();
		for (i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				System.out.print(" " + G[i][j]);
			}
			System.out.println(" ");
		}
		if(firstExecution==1){
			for ( int h=0;h<k;h++){
				System.out.println(serverInserted[h]);
				index.add(serverInserted[h]);
			}
		}
		for ( int s:index){
			System.out.println(s);
		}
		

//		for (int p = 0; p < k; p++) {
//			// System.out.println(" diagonal matrix");
//			// printMatrix(G, k, N_new);
//			for (int l = 0; l <= p - 1; l++) {
//				int alpha = -(G[l][p] / G[p][p]);
//				for (int j = p; j < k; j++) {
//					G[l][j] = G[l][j] ^ (alpha & G[p][j]);
//				}
//			}
//			System.out.println(" upper triangle");
//			printMatrix(G, k, k);
//		}

		return index;

	}

	public void decodePacketsVer2(int[][] G, ArrayList<Integer> sourceIndex) {
		// ArrayList<BitSet> ec = encodedFragments;
		// System.out.println(" original matrix");
		// printMatrix(G, k, N_new);
		// this.encodedFragments= encodedFragments;

		int[][] newGenerator = new int[k][k];
		int l = 0;
		for (int i : sourceIndex) {
			for (int j = 0; j < k; j++) {
				newGenerator[l][j] = G[i][j];
			}
			l++;
		}
		printMatrix(newGenerator, k, k);

		int n = k;
		int N = k;
		// ArrayList<String> decodedString = new ArrayList<String>();
		for (int p = 0; p < n; p++) {
			int max = p;
			for (int i = p + 1; i < N; i++) {
				if (Math.abs(newGenerator[i][p]) > Math
						.abs(newGenerator[max][p])) {
					max = i;
				}
			}
			int[] temp = newGenerator[p];
			newGenerator[p] = newGenerator[max];
			newGenerator[max] = temp;

			// System.out.println(" diagonal matrix");
			// printMatrix(G, k, N_new);

			if (Math.abs(newGenerator[p][p]) != 1) {
				throw new RuntimeException(
						"Matrix is singular or nearly singular");
			}

			for (int i = p + 1; i < N; i++) {
				int alpha = -(newGenerator[i][p] / newGenerator[p][p]);
				int index = i;
				for (int j = p; j < n; j++) {
					newGenerator[i][j] = newGenerator[i][j]
							^ (alpha & newGenerator[p][j]);
				}
			}
			System.out.println(" lower triangle is decode n the fly");
			printMatrix(newGenerator, k, k);
			for (int i = 0; i <= p - 1; i++) {
				int alpha = -(newGenerator[i][p] / newGenerator[p][p]);
				int index = i;
				for (int j = p; j < n; j++) {
					newGenerator[i][j] = newGenerator[i][j]
							^ (alpha & newGenerator[p][j]);
				}
			}
			// System.out.println(" upper triangle");
			// printMatrix(newGenerator, k, N_new);
		}
	}

	void printMatrix(int[][] G, int k, int N_new) {
		for (int i = 0; i < N_new; i++) {
			for (int j = 0; j < k; j++) {
				System.out.print(" " + G[i][j]);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {

		OnTheFlyGaussianElimination o = new OnTheFlyGaussianElimination();
		o.createGeneratorMatrix();
		o.transpose = o.matrixTranspose(o.matrix);
		// int[] servers=o.serverAvailability();
		int[] servers = { 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
				1, 0 };
		int created = 0;
		int shouldExecute = 1;
		int idx = 0;
		int serverNumber = 0;

		while (created < o.k) {
			if (shouldExecute == 1) {
				o.decodeOnTheFly(o.transpose, serverNumber);
				shouldExecute = 0;
			}
			Iterator<Integer> iter = o.index.iterator();
			while (iter.hasNext()) {
				serverNumber = iter.next();
				System.out.println("\n" + serverNumber + ":"
						+ servers[serverNumber]);
				if (servers[serverNumber] == 0) {
					for (int j = 0; j < o.k; j++) {
						o.transpose[serverNumber][j] = 0;
						// o.G[created][j]=0;
					}
					idx = o.index.indexOf(serverNumber);
					created = 0;
					shouldExecute = 1;
					break;
				} else {
					created++;
				}
			}

		}
		o.G = null;
		o.decodePacketsVer2(o.transpose, o.index);
	}

}
